package com.aurora.leetcode.answer;

/**
 * @author : Aurora
 * @date : 2024/4/19 09:55
 * @description
 * 你可以选择使用单链表或者双链表，设计并实现自己的链表。
 * 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
 * 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
 * 实现 MyLinkedList 类：
 * MyLinkedList() 初始化 MyLinkedList 对象。
 * int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
 * void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
 * void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
 * void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
 * void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
 * <p>示例
 * <p>输入
 * ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
 * [[], [1], [3], [1, 2], [1], [1], [1]]
 * <p>输出
 * [null, null, null, null, 2, null, 3]
 * <p>解释
 * MyLinkedList myLinkedList = new MyLinkedList();
 * myLinkedList.addAtHead(1);
 * myLinkedList.addAtTail(3);
 * myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
 * myLinkedList.get(1);              // 返回 2
 * myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
 * myLinkedList.get(1);              // 返回 3
 */
public class DesignLinkedList_707 {
    //对于双向链表而言，操作index时，可以考虑使用head或tail优化
    //大于size/2时使用head反之使用tail
    private Node head;//头节点
    private Node tail;//尾节点
    private int count;//元素个数
    class Node{
        public Node(){

        }
        public Node(int val){
            this.val = val;
        }
        private int val;
        private Node next = null;
        private Node pre = null;

    }

    public DesignLinkedList_707() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        head.pre = tail;
        tail.pre = head;
        tail.next = head;
    }

    public int get(int index) {
        Node p = head.next;
        if(index >= count || index < 0){
            return -1;
        }
        for (int i=0;p!=tail && i<count;p=p.next,++i){
            if(i == index){
                return p.val;
            }
        }
        return -1;
    }

    public void addAtHead(int val) {
        Node node = new Node(val);
        node.next = head.next;
        node.pre = head;
        head.next = node;
        node.next.pre = node;
        if(count == 0){
            tail.pre = node;
        }
        count++;
    }

    public void addAtTail(int val) {
        Node node = new Node(val);
        if(count == 0){
            head.next = node;
            tail.pre = node;
            node.next = tail;
            node.pre = head;
        }else{
            node.pre = tail.pre;
            node.next = tail;
            tail.pre.next = node;
            tail.pre = node;
        }
        ++count;
    }

    public void addAtIndex(int index, int val) {
        if(index > count)return;
        if(index == count){
            addAtTail(val);
            return;
        }
        Node p = getAtIndexNode(index);
        if(p == null)return;
        Node newNode = new Node(val);
        newNode.next = p;
        newNode.pre = p.pre;
        newNode.pre.next = newNode;
        p.pre = newNode;
        ++count;
    }
    public Node getAtIndexNode(int index){
        int i=0;
        Node p = head.next;
        while(i < count){
            if(i == index){
                return p;
            }
            p = p.next;
            ++i;
        }
        return null;
    }

    public void deleteAtIndex(int index) {
        if(index < 0 || index >=count){
            return;
        }
        Node p = getAtIndexNode(index);
        if(p == null)return;
        p.pre.next = p.next;
        p.next.pre = p.pre;
        --count;
    }

    public static void main(String[] args) {
        DesignLinkedList_707 linkedList = new DesignLinkedList_707();
//        linkedList.addAtHead(7);
//        linkedList.addAtHead(2);
//        linkedList.addAtHead(1);
//        linkedList.addAtTail(3);
        linkedList.addAtIndex(0,10);
        linkedList.addAtIndex(0,20);
        linkedList.addAtIndex(1,30);
//        linkedList.deleteAtIndex(2);
//        System.out.println("func-get:"+linkedList.get(3));
//        linkedList.deleteAtIndex(1);
        printLinkedList(linkedList);
    }


    private static void printLinkedList(DesignLinkedList_707 linkedList){
        Node p = linkedList.head.next;
        System.out.println("打印链表：");
        while(p != linkedList.tail){
            System.out.print(p.val+",");
            p = p.next;
        }
        System.out.println();
        System.out.println("链表中元素个数："+linkedList.count);
    }



}
